MUYI · 后端工程师的生产级知识体系

Appearance

1、简介 ​

CAS（Compare and Swap），即比较并替换，是实现并发算法时常用到的一种技术。Doug lea大神在java同步器中使用了CAS技术，鬼斧神工的实现了多线程执行的安全性。原先在JDK低版本的时候，计算机底层硬件还不具备提供CAS的能力支持。后续因为计算机底层指令集的发展，才支持了CAS的衍生。

CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B。当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。其中以Unsafe中compareAndSwapint为例看下JDK1.8中方法声明以及参数说明：

java
// 第一个参数为持有cas属性的对象；
// 第二个参数代表的含义为：要比较的值字段相对于对象的起始内存地址的字节偏移；
// 第三个是外部传入待比较的值（旧的值）；
// 第四个值为待更准备更新的数据。
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);

和CAS相关的一个概念是原子操作。原子是不能被进一步分割的最小粒子，而原子操作则是不可被中断的一个或一系列操作。而CAS则是Java中保证原子操作的一种方式。从Java1.5开始，JDK的并发包里就提供了一些类来支持原子操作，都是以Atomic开头。

之前讲volatile的时候说过，volatile不能保证类似i++这样操作的原子性。CAS能够保证原子性的原理，得从JVM指令说起。

2、原理分析 ​

Atomic包下的类都调用了Unsafe的compareAndSwap*方法来实现CAS操作，它是一个本地方法，实现位于unsafe.cpp中。

java
UNSAFE_ENTRY(jboolean, Unsafe_CompareAndSwapInt(JNIEnv *env, jobject unsafe, jobject obj, jlong offset, jint e, jint x))
  UnsafeWrapper("Unsafe_CompareAndSwapInt");
  oop p = JNIHandles::resolve(obj);
  jint* addr = (jint *) index_oop_from_field_offset_long(p, offset);
  return (jint)(Atomic::cmpxchg(x, addr, e)) == e;
UNSAFE_END

可以看到它通过Atomic::cmpxchg来实现比较和替换操作。其中参数x是即将更新的值，参数e是原内存的值。

如果是Linux的x86，Atomic::cmpxchg方法的实现如下：

java
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
  int mp = os::is_MP();
  __asm__ volatile (LOCK_IF_MP(%4) "cmpxchgl %1,(%3)"
                    : "=a" (exchange_value)
                    : "r" (exchange_value), "a" (compare_value), "r" (dest), "r" (mp)
                    : "cc", "memory");
  return exchange_value;
}

而windows的x86的实现如下：

java
inline jint Atomic::cmpxchg (jint exchange_value, volatile jint* dest, jint compare_value) {
    int mp = os::isMP(); //判断是否是多处理器
    _asm {
        mov edx, dest
        mov ecx, exchange_value
        mov eax, compare_value
        LOCK_IF_MP(mp)
        cmpxchg dword ptr [edx], ecx
    }
}

// Adding a lock prefix to an instruction on MP machine
// VC++ doesn't like the lock prefix to be on a single line
// so we can't insert a label after the lock prefix.
// By emitting a lock prefix, we can define a label after it.
#define LOCK_IF_MP(mp) __asm cmp mp, 0  \
                       __asm je L0      \
                       __asm _emit 0xF0 \
                       __asm L0:

如果是多处理器，为cmpxchg指令添加lock前缀。反之，就省略lock前缀（单处理器会不需要lock前缀提供的内存屏障效果）。这里的lock前缀就是使用了处理器的总线锁（最新的处理器都使用缓存锁代替总线锁来提高性能）。

cmpxchg(void* ptr, int old, int new)，如果ptr和old的值一样，则把new写到ptr内存，否则返回ptr的值，整个操作是原子的。在Intel平台下，会用lock cmpxchg来实现，使用lock触发缓存锁，这样另一个线程想访问ptr的内存，就会被block住。

更多lock指令相关的可以参考之前写volatile的一篇文章：【细谈Java并发】内存模型之volatile

3、CAS的三大问题 ​

3.1、ABA问题 ​

因为CAS需要在操作值的时候检查值有没有发生变化，比如没有发生变化则更新。但是如果一个值原来是A，变成了B，又变成了A，那么用CAS检查时就会发现它的值没有发生变化。但是值却变化了。

ABA问题的解决思路就是使用版本号。在变量前面追加上版本号，每次变量更新的时候把版本号加1，那么A->B->A就会变成1A->2B->3A。

从Java 1.5开始，JDK的Atomic包里提供了一个类AtomicStampedReference来解决ABA问题。这个类的compareAndSet方法的作用是：首先检查当前引用是否等于预期引用。并且检查当前标志是否等于预期标志。如果全部相等，则以原子方式将该引用和该标志的值设置为给定的更新值。

3.2、循环时间长开销大 ​

自旋CAS如果长时间不成功，会给CPU带来大的执行开销。如果JVM能支持处理器提供的pause指令，那么效率会有一定的提升。pause指令有两个作用：

  • 第一，它可以延迟流水线执行命令（de-pipeline），使CPU不会消耗过多的执行资源。延迟的时间取决于具体实现的版本，在一些处理器上延迟时间是零；
  • 第二，它可以避免在退出循环的时候因内存顺序冲突（Memory Order Violation）而引起CPU流水线被清空（CPU Pipeline Flush）。从而提高CPU的执行效率。

3.3、只能保证一个共享变量的原子操作 ​

当对一个共享变量执行操作时，我们可以使用循环CAS的方式来保证原子操作。但是对多个共享变量操作时，循环CAS就无法保证操作的原子性。这个时候就可以用锁。

还有一个取巧的办法，就是把多个共享变量合并成一个共享变量来操作。比如，有两个共享变量i = 2，j = a，合并成ij = 2a，然后用CAS来操作ij。

从Java 1.5开始，JDK提供了AtomicReference类来保证引用对象之间的原子性。这样就可以把多个变量放在一个对象里做CAS操作。